package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/house-robber/description/?envType=study-plan-v2&envId=top-100-liked
 * <p>
 * 参考视频：b23.tv/pc522x3
 * 参考通过
 *
 * @author yulongTian
 * @create 2024-07-20 11:04
 */
public class Test79 {
    public static void main(String[] args) {
        System.out.println(new Test79().rob(new int[]{2, 7, 9, 3, 1}));
    }

    /*
    f(i) = max( f(i - 1), f(i - 2) + nums[i])
     */
    public int rob(int[] nums) {
        int[] cache = new int[nums.length];
        Arrays.fill(cache, -1);
        return dfs(nums.length - 1, nums, cache);
    }

    public int dfs(int i, int[] nums, int[] cache) {
        if (i < 0) {
            return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }
        int res = Math.max(dfs(i - 1, nums, cache), dfs(i - 2, nums, cache) + nums[i]);
        cache[i] = res;
        return res;
    }

}
